package sort;

/**
 * 选择排序
 */

/**
 * 时间复杂度：O(N*N)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 */
public class SelectSort implements ISort{
    @Override
    public void sort(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int maxIndex = left;
            int minIndex = left;
            for(int i = left + 1; i <= right; i++) {
                if(array[minIndex] > array[i]) {
                    minIndex = i;
                }
                if(array[maxIndex] < array[i]) {
                    maxIndex = i;
                }
            }
            Swap.swap(array,left,minIndex);

            if(maxIndex == left) {
                maxIndex = minIndex;
            }
            Swap.swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
}
